{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "0187cfb0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "公钥 (N, x): (10097063, 5)\n",
      "私钥 (p, q): (1009, 10007)\n",
      "原始消息明文: 1010\n",
      "密文: [503618, 3615508, 895801, 3400705]\n",
      "解密消息: 1010\n"
     ]
    }
   ],
   "source": [
    "## Goldwasser-Micali (GM)  加密算法\n",
    "\n",
    "from sympy.ntheory import is_quad_residue, primerange\n",
    "from random import randint\n",
    "\n",
    "def generate_keys():\n",
    "    p = next(primerange(1000, 10000))\n",
    "    q = next(primerange(10000, 11000))\n",
    "    n = p * q\n",
    "    x = 2\n",
    "    while is_quad_residue(x, p) and is_quad_residue(x, q):\n",
    "        x += 1\n",
    "    return (n, x), (p, q)\n",
    "\n",
    "def encrypt(message, public_key):\n",
    "    n, x = public_key\n",
    "    encrypted = []\n",
    "    for bit in message:\n",
    "        r = randint(1, n-1)\n",
    "        c = (r * r * x**int(bit)) % n\n",
    "        encrypted.append(c)\n",
    "    return encrypted\n",
    "\n",
    "def decrypt(encrypted, private_key):\n",
    "    p, q = private_key\n",
    "    decrypted = \"\"\n",
    "    for c in encrypted:\n",
    "        if is_quad_residue(c, p) and is_quad_residue(c, q):\n",
    "            decrypted += \"0\"\n",
    "        else:\n",
    "            decrypted += \"1\"\n",
    "    return decrypted\n",
    "\n",
    "# 示例\n",
    "public_key, private_key = generate_keys()\n",
    "message = \"1010\"\n",
    "encrypted_message = encrypt(message, public_key)\n",
    "decrypted_message = decrypt(encrypted_message, private_key)\n",
    "\n",
    "print(\"公钥 (N, x):\", public_key)\n",
    "print(\"私钥 (p, q):\", private_key)\n",
    "print(\"原始消息明文:\", message)\n",
    "print(\"密文:\", encrypted_message)\n",
    "print(\"解密消息:\", decrypted_message)\n",
    "\n",
    "## 输出样例\n",
    "# 公钥 (N, x): (10097063, 5)\n",
    "# 私钥 (p, q): (1009, 10007)\n",
    "# 原始消息明文: 1010\n",
    "# 密文: [4261321, 8377247, 969148, 6082662]\n",
    "# 解密消息: 1010\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "36ab833e",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
